import java.awt.Point;
import java.util.ArrayList;

public class TSP {
	class Point{
		double x;
		double y;
	}

	ArrayList<Point> cities;
	int size;
	double [][]distances;
	
	void InitData(){
		DataReader reader = new DataReader();
		reader.SetFilename("C:\\tmp\\algorithm\\testTSP18.txt");
		
		String str;
		str = reader.GetNextLine();		
		size = Integer.parseInt(str);
		
		cities = new ArrayList<Point>(size);
		distances = new double[size][size];
		
		while((str = reader.GetNextLine()) != null)
		{
			String[] parser = str.split(" ");
			Point pos = new Point();
			pos.x = Double.parseDouble(parser[0]);
			pos.y = Double.parseDouble(parser[1]);
			cities.add(pos);
		}
		
		//init distances
		for(int i = 0; i < size; i++)
		{
			for(int j = 0; j < size; j++){
				if(i == j){
					distances[i][j] = 0;
				}
				else
				{
					Point pos1 = cities.get(i);
					Point pos2 = cities.get(j);
					distances[i][j] = Math.sqrt((pos1.x - pos2.x) * (pos1.x - pos2.x) + (pos1.y - pos2.y)*(pos1.y - pos2.y));
				}
			}
		}
	}
	
	
	public void PrintData(){
		for(int i = 0; i < size; i++)
		{
			Point pos = cities.get(i);
			System.out.println(pos.x + " " + pos.y);
		}
		
		System.out.print("\n");
		
		for(int i = 0; i < size; i++)
		{
			for(int j = 0; j < size; j++){
				System.out.print(distances[i][j] + " ");
			}
			
			System.out.print("\n");
		}		
	}
	
	
	public void RunTSP(){
		for(int m = 2; m <= size; m++)
		{
			//get list of SubSetS
			//GetSubSetS(m);
			//for each j in SubSetS j != 1
			//A[s, j] = min k c S, k != j, {A[S-{j}, k] + Ckj}
		}
		
		//return min j=2, ..., n{A[1, 2, ..., n], j] + cj1}
	}
}
